home *** CD-ROM | disk | FTP | other *** search
/ Floppyshop 2 / Floppyshop - 2.zip / Floppyshop - 2.iso / diskmags / 5791-.end / dmg-6143 / lza_rept / compres5.txt < prev   
Text File  |  1997-02-18  |  7KB  |  134 lines
  1.                 Experiments in Data Compression V
  2.           (or "It seemed like a good idea at the time")
  3.                          by John Kormylo
  4.                          E.L.F. Software
  5.  
  6.  
  7. State of the Art
  8.  
  9.      Since  Report  IV,  I  have fixed a couple of  bugs  in  the 
  10. "Smart" algorithm.  The current comparisons are as follows:
  11.  
  12.            | DEMONSTR.DOC | ELFBACK.PRG | WORDLIST.TXT |
  13. -----------+--------------+-------------+--------------+
  14.     ZIP    |       25134  |      32417  |      496876  |
  15.   Best 16K |       21960  |      32372  |      446606  |
  16.  Smart 16K |       22076  |      32359  |      489471  |
  17.  Smart 8K  |       22214  |      32190  |      483486  |
  18. -----------+--------------+-------------+--------------+
  19.  Adapt 8K  |       22317  |      32057  |      484332  |
  20. -----------+--------------+-------------+--------------+
  21.  
  22. The  "16K"  and "8K" refer to the number of entries in  the  main 
  23. dictionary.   Note  that the "Smart" method now out-performs  the 
  24. "Best" method on one of the files.
  25.      Unfortunately,  the results were not so good when  archiving 
  26. ELFARC v1.4, as shown by the following table:
  27.  
  28.            | ELFARC.PRG | ELFARC.RSC |  READ_ME  |
  29. -----------+------------+------------+-----------+
  30.     ZIP    |     32988  |      6255  |     1000  |
  31.   Best 16K |     33143  |      6314  |     1037  |
  32.  Smart 8K  |     33107  |      6305  |     1028  |
  33. -----------+------------+------------+-----------+
  34.  Adapt 8K  |     32978  |      6192  |     1043  |
  35. -----------+------------+------------+-----------+
  36.  
  37. Emulating the Competition
  38.  
  39.      A number of tests were made to make LZA more like ZIP.  Most 
  40. changes (such as increasing the maximum match length to 256 bytes 
  41. or adding every possible string to the dictionary) resulted in  a 
  42. loss of performance.
  43.      One  feature of LZA which has never really been  tested  for 
  44. effectiveness is the "new character" code.   Instead of assigning 
  45. and  initial  count of 1 to each of the 320 possible  codes  (256 
  46. ASCII  and 64 length),  LZA uses a "new character" code which  is 
  47. followed by the character to be added.    The reason for this  is 
  48. to  improve the performance on text files,  where only  about  96 
  49. ASCII  characters are ever used.   However,  it also  imposes  an 
  50. overhead which is never recovered for binary files or short  text 
  51. files, which is primarily what archive programs are used for.
  52.      Removing  the "new character" code is a funndamental  change 
  53. in  the LZA format.   Consequently a number of other  fundamental 
  54. changes which had not been implemented previously simply  because 
  55. they  were fundamental (such as sorting the codes  by  frequency) 
  56. were also implemented.
  57.      First,  the  code set was reduced to 258 (256 ASCII and  one 
  58. each for the FIFO buffer and main dictionary).   The length  code 
  59. was implemented separately,  also using full adaptive.   This was 
  60. done  so  that the ASCII codes would not be penalized  by  counts 
  61. associated  with  all the length codes (using  256  length  codes 
  62. instead of 64 would have added 1 bit to every character, at least 
  63. initially).   The FIFO lag and dictionary range codes remained as 
  64. before.
  65.      The  results  for  this new method are shown  in  the  above 
  66. tables as "Adapt 8K."  As expected,  it performed slightly  worse 
  67. on text files,  but better on binary files.  More importantly, it 
  68. beat ZIP on every file but one.
  69.  
  70. FIFO Buffer - Layered Binary Search Tree
  71.  
  72.      While using a hash table for the FIFO buffer is simpler  and 
  73. probably faster for searches,  using a layered binary search tree 
  74. takes  much  less RAM and adds and removes entries  much  faster.  
  75. The resulting tree will use less than 2K RAM,  as opposed to  64K 
  76. RAM for the hash table (for a maximum match length of 65  bytes). 
  77. The speed advantage is best illustrated by noting that the entire 
  78. FIFO buffer is replaced every 64 entries.
  79.      The  search tree used for the FIFO table differs  from  that 
  80. used in the main dictionary in that it includes an index into the 
  81. table of string pointers.
  82.  
  83. typedef struct fifo {
  84.   struct fifo *child1;    /* less than */
  85.   struct fifo *child2;    /* greater than */
  86.   struct fifo *next;      /* start of next tree */
  87.   unsigned char *text;    /* string pointer */
  88.   unsigned int sum;       /* sum of all children */
  89.   unsigned char len;      /* number of common chars */
  90.   unsigned char test;     /* first uncommon char */
  91.   int index;              /* fifo table index */
  92.  } FIFO;
  93.  
  94. One  could drop the text pointer and use the text  pointer  array 
  95. index, but it is faster to keep it.
  96.      This  search tree also differs from the main  dictionary  in 
  97. how  it  adds and removes entries.   The main dictionary  used  a 
  98. fixed  array  of 8K (or 16K) entries,  with the  duplicate  nodes 
  99. coming from the free structure list.   When removing a node,  one 
  100. must also search the remaining layers for duplicates.
  101.      The  FIFO  buffer allocates all of its nodes from  the  free 
  102. structure  list.   Whenever a new string is added,  the text  and 
  103. index  values for its matches within each layer are set  to  this 
  104. (latest)  entry,  so  that one will always find the  most  recent 
  105. match.   This also means that when it is time to remove an entry, 
  106. there will be no duplicates remaining in the tree.
  107.      There was about a 15% improvement in speed from this change.
  108.  
  109.      One  could  use a common tree structure for  both  the  FIFO 
  110. buffer  and  main  dictionary by adding the  index  to  the  main 
  111. dictionary  and replacing or augmenting the text entry with a  an 
  112. array of string pointers (refered to by index).  While this would 
  113. simplify  the  code,  allowing common functions  for  adding  and 
  114. removing entries, it would be slower and use more RAM.
  115.  
  116. Tweaking the Code
  117.  
  118.      Using  Pure Profiler I was able to improve some of the  code 
  119. w.r.t. speed.  One thing I noticed is that Pure C compiled
  120.  
  121.      while(p) {
  122.           if(p->test == ref) break;
  123.           else if (p->test > ref) p = p->child1;
  124.           else p = p->child2;
  125.       }
  126.  
  127. using  two  compares  instead of one compare  and  two  branches.  
  128. Since  over 10% of the CPU time is spent on this  type  operation 
  129. (namely  binary searches),  I tried replacing this loop  with  an 
  130. assembly language function.   However,  the overhead for  calling 
  131. the  function  about equalled the advantage  of  eliminating  the 
  132. duplicate compare.
  133.  
  134.